
public class MergeSort<Type extends Comparable<Type>> extends SorterParent<Type>{

	@Override
	public Type[] sort(Type[] toSort, String method) {
		super.sort(toSort, method);
		
		Type[] tmp = (Type[]) new Comparable[toSort.length];
		mergeSort(toSort, tmp, 0, toSort.length - 1);
		
		endTime = System.nanoTime();
		log.add("End of log. Nanotime is: " + endTime);
		return toSort;
	}	
	
	private void mergeSort(Type[] toSort, Type[] tmp, int left, int right){
		steps++;
		
		if(left < right){
			int center = (left + right) / 2;
			mergeSort(toSort, tmp, left, center);
			mergeSort(toSort, tmp, center + 1, right);
			merge(toSort, tmp, left, center + 1, right);
		}
	}
	
	private void merge(Type[] toSort, Type[] tmp, int leftPos, int rightPos, int rightEnd){
		int leftEnd = rightPos -1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;
		
		steps++;
		log.add("		Comparing numbers in main while-loop \n");
		while(leftPos <= leftEnd && rightPos <= rightEnd){
			if(toSort[leftPos].compareTo(toSort[rightPos]) <= 0){
				tmp[tmpPos++] = toSort[leftPos++];
			}
			else{
				tmp[tmpPos++] = toSort[rightPos++];
			}
		}
		//Kopieer rest van linkerhelft
		log.add(" 		Copying left half to temporary \n");
		while(leftPos <= leftEnd){
			tmp[tmpPos++] = toSort[leftPos++];
		}
		//Kopieer rest van rechterhelft
		log.add(" 		Copying right half to temporary \n");
		while(rightPos <= rightEnd){
			tmp[tmpPos++] = toSort[rightPos++];
		}
		//Kopieer tmp weer terug
		log.add(" 		Putting numbers back \n");
		for(int i=0; i < numElements; i++, rightEnd--){
			toSort[rightEnd] = tmp[rightEnd];
		}
	}
}
